halting problem

Definition

The function $\mathtt{HALT}$ takes input $\langle \alpha, x \rangle$ and outputs $1$ iff TM $M_\alpha$ represented by $\alpha$ halts on input $x$ within a finite number of steps.

Theorem

$\mathtt{HALT}$ is not computable by any TM.

See also

• Theorem, Turing machine non-computable function
• Rice's theorem
• Lawvere's fixed-point theorem

References

1. S. Arora, B. Barak. Computational Complexity: A Modern Approach, Cambridge University Press, 2009, pp. 22-23.
2. N. D. Jones, Computability and complexity: from a programming perspective. in Foundations of computing. Cambridge, Mass: MIT Press, 1997, pp. 16-17.